数据结构 |
您所在的位置：网站首页 › 数据结构p->next->prior › 数据结构 |
数据结构
|
1.介绍
单链表有很大的局限，因为它每一个结点的指针域存放了下一个结点的地址，因此它只能够单向的遍历。 如果我们想要反向遍历，又该怎么办呢？ 如果只用单链表，我们可以依次使用moveTo函数遍历每个下标的元素，但这样每遍历一个元素时间复杂度就是O（n），遍历所有元素那将会是O（n²）。 因此，我们将会在每个结点多加一个指针pre，指向上一个结点，这样的话，就是以空间换取时间，反向遍历的时间复杂度就会优化到O（n）。 因此，结点的结构如下：
这样一个指针指向前结点，一个指针指向后结点。这样，双链表结构如下：
我们着重讲和单链表不同的两个操作插入和删除。 （1）插入 template bool DLinkList::insert(int i, const T& val) { //p是要插入结点的前一个结点 node* p = moveTo(i - 1); if (!p) return false; //插入结点为q node* q = new node(val,p,p->next); //到这里我们并没改变p和p原来的下一个结点 if (p->next)//防止p为尾结点 p->next->pre = q; p->next = q; return false; }注意上面第二个if语句，单链表是不需要考虑直接后继结点的，但双链表需要。 我们需要考虑是否是插入链表尾，如果是，则if语句不用执行，因为此时pre->next为nullptr。 （2）删除 template bool DLinkList::remove(int i) { node* p = moveTo(i - 1); if (!p) return false; //其实传入length上面是不会出错的，但我们不能删除length下标的元素 node* q = p->next; if (!q)//防止出界 return false; p->next = q->next; if(p->next) p->next->pre = p; delete q; }同插入时一样，需要考虑删除尾节点。 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |